//
// Created by denglibin on 2021/5/28.
// 并查集：
//一种用于管理分组的数据结构。它具备两个操作：(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。

//注意：并查集不能将在同一组的元素拆分为两组。

//并查集的实现：
//用树来实现。
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <stdlib.h>
typedef struct node{
    int v; //当前节点的值
    struct node* parent; //父节点
}Node;

/**
 * 初始化一个节点
 * @param x
 */
static Node* initNode(int v){
    Node* node = (Node*)malloc(sizeof(Node));
    node->v = v;
    node->parent = node; //默认父节点就是自己
    return node;
}
/**
 * 是否内存
 * @param node
 */
static void freeNode(Node* node){
    free(node);
}


/**
 * 查找根节点
 * @param node
 * @return
 */
static Node* findRoot(Node* node){
    if(node->parent == node){//当前节点就是根节点
        return node;
    }
    return findRoot(node->parent); //查找父节点的根节点
}
/**
 * 合并两个节点所在的集合
 * @param node1
 * @param node2
 */
static void unit(Node* node1, Node* node2){
    //先查找两个节点的根节点
    Node* root1 = findRoot(node1);
    Node* root2 = findRoot(node2);
    if(root1 == root2){ //已经是在同一个集合中了
        return;
    }
    root2->parent = root1; //将root2挂着root1下，实现两个集合的合并
}

/**
 * 判断两个节点是否属于同一个集合
 * @param node1
 * @param node2
 */
static int same(Node* node1, Node* node2){
    return findRoot(node1) == findRoot(node2);
}

